1154F - Shovels Shop - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
#define no cout << "no\n"
#define yes cout << "yes\n"
#define endl "\n"
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while(0)
void err(){cout<<"\n";}
template<class T,class... Ts>
void err(T arg,Ts... args){
	cout<<arg<<" ";
	err(args...);
}

const int N = 200005;

int n, m, k, m_=0, p[N];
ll f[N], a[N];

void solve() {
	cin>>n>>m>>k; a[0]=0; 
	for(int i = 1; i <= n; i++) { cin>>a[i]; p[i]=0; }
	sort(a+1,a+1+n);
//	n=k;
	for(int i = 1; i <= m; i++) {
		int x,y;
		cin>>x>>y;
		p[x] = max(p[x], y);
	}
	for(int i = 1; i <= n; i++) a[i] += a[i-1];
	for(int i = 1; i <= k; i++)
		for(int j = 0; j < i; j++)
			f[i] = max(f[i], f[j] + a[j+p[i-j]]-a[j]);
	
	cout << a[k]-f[k] << endl;
}
		

signed main(){
	IOS;
	int T=1;
//	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}